package com.crazyxmq.linear;

import java.util.Iterator;

/*
* 双向链表
*
* */
public class TwoWayLinkList<T> implements Iterable<T>{

    // 头节点
    private Node head;

    // 记录首节点
    private Node first;

    // 记录尾节点
    private Node last;

    // 记录链表长度
    private int N;


    //节点类
    private class Node{
        T item;
        Node pre;
        Node next;

        public Node(T item,Node pre, Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }


    public TwoWayLinkList() {
        //初始化头节点
       this.head = new Node(null,null,null);
       this.last = null;
       //初始化个数
        this.N = 0;

    }

    // 空置链表
    public void clear(){
        //把头节点的下一个节点断掉
        head.next = null;
        this.last = null;
        this.N = 0;
    }

    // 判断线性表是否为空
    public boolean isEmpty(){
        return N == 0;
    }

    // 获取线性表中元素的个数
    public int length(){
        return N;
    }

    // 获取第一个元素
    public T getFirst(){
        if(isEmpty()){
            return null;
        }
        return head.next.item;

    }
    // 获取最后一个元素是
    public T getLast(){
        if(isEmpty()){
            return null;
        }
        return last.item;

    }

    // 读取并返回线性表-单向链表的第i个元素的值
    public T get(int i){
        //通过循环，从头开始，找i次
        Node n = head.next;
        for (int index = 0; index < i; index++){
            n = n.next;
        }
        return n.item;
    }

    // 往线性表中插入元素
    public void insert(T t){
        if(isEmpty()){
            // 如果链表为空,创建新的节点,并让头节点指向尾节点
            Node newNode = new Node(t, head, null);
            last = newNode;
            head.next = last;
        }else{
            Node oldLast = last;
            // 创建一个新节点，新节点的上一个节点应该尾节点指向last
            Node newNode = new Node(t, oldLast, null);

            // 让当前的尾结点 指向新结点
            oldLast.next = newNode;
            //让新结点成为尾节点
            last = newNode;
        }


        // 元素个素+1
        N++;

    }


    public void insert(int i ,T t){
        // 找到i位置的前一个节点
        Node pre = head;
        for (int index = 0; index<= i-1;index++){
            pre = pre.next;
        }
        // 找到i位置的节点
        Node curr = pre.next;

        // 创建一个新的节点
        Node newNode = new Node(t, pre,curr);
        // 让前一个节点的下一个节点指向当前节点
        pre.next = newNode;
        // 让i位置的先前节点指向新节点
        curr.pre = newNode;
        N++;
    }




    //[1,2,3,4,5] N=5
    // 0 1 2 3 4
    public T remove (int i){
       // 找到 i 位置的前一个节点
        Node pre = head;
        for (int index = 0; index<= i-1;index++){
            pre = pre.next;
        }
        // 找到i 位置的节点
        Node curr = pre.next;
        // 找到 i 位置后面的一个节点
        Node nextNode= curr.next;
        // 上一个节点指向下一个节点
        pre.next = nextNode;

        nextNode.pre = pre;
        // 元素个数 - 1
        N--;

        return curr.item;
    }

    public int indexOf(T t){
       // 从头节点开始，依次找到每一个节点
        Node n = head;
        for (int i = 0;n.next!=null;i++){
            n = n.next;
            if(n.item.equals(t)){
                return i;
            }
        }

        return -1;
    }


    @Override
    public Iterator<T> iterator() {
        return new TIterator();
    }



    private class TIterator implements Iterator{

        private Node n;

        public TIterator(){
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next!= null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
}
